A binary adder is an elementary electronic circuit that adds two binary operands to obtain a binary resultant. An adder that is capable of adding two operands along with a carry-in to obtain a resultant and a carry-out is known as a full adder. Full adders can be coupled in series with the carry-out of one full adder coupled to the carry-in of a next adder to implement a binary adder of greater width.
FIG. 1 illustrates a known 16-bit carry-skip adder 100 having a carry-in (“CI”) and a carry-out (“CO”). Carry-skip adder 100 includes propagate-generate-kill (“PGK”) stages 105, carry-skip cells 110, and sum cells 115 (only a portion of the elements are labeled so as not to clutter FIG. 1). CI0 represents the carry-in for PGK stage 0. If PGK stage 0 receives a CI0 (i.e., CI=“1”), PGK stage 0 can either propagate the CI0 as a carry-out 120 to be receive as a carry-in 125 to PGK stage 1 or kill the CI0, such that PGK stage 1 does not receive carry-in 125. If PGK stage 0 does not receive a CI0 (i.e., CI=“0”), then PGK stage 0 can generate carry-out 120 to be received as carry-in 125 to PGK stage 1. Each of PGK stages 105 will either propagate, generate, or kill a carry-in dependent upon the value of the two operand bits corresponding to its bit position.
Sum cells 115 act to sum a carry-in bit with two operand bits having equivalent bit positions to generate a resultant bit of a multi-bit resultant. However, before each sum cell 115 can generate a resultant bit, the corresponding carry-in must be determined. To determine a carry-in, CI0 must be given an opportunity to propagate from PGK stage 0 to PGK stage 15. As such, propagation of carry-ins is a limiting speed factor.
To accelerate the propagation of carry-ins through carry-skip adder 100, PGK stages 105 are coupled into groups by carry-skip cells 110. Corresponding groups of the operands are analyzed to determine whether a carry-in to a group of PGK stages 105 will propagate through the entire group of PGK stages 105. If this condition is true, then the carry-skip cell will skip the carry-in to the group over the group and provide the carry-in to the next group of PGK stages 105. Skipping groups of PGK stages 105 via carry-skip cells 110 incurs less delay than waiting for the carry-in to propagate through each PGK stage of the group. However, even with carry-skip cells 110, propagation of carry-ins through carry-skip adder 100 is still a limiting speed factor.